package com.gaogzhen.datastructure.graph.directed;

import com.gaogzhen.datastructure.graph.undirected.Entry;
import com.gaogzhen.datastructure.stack.Stack;
import edu.princeton.cs.algs4.Digraph;

import java.util.Iterator;

/**
 *  检测有向环
 * @author gaogzhen
 */
public class DirectedCycle {

    /**
     * 标记
     */
    private boolean[] marked;

    /**
     * 指向起点的有向路径
     */
    private int[] edgeTo;

    /**
     * 当前栈上顶点
     */
    private boolean[] onStack;

    /**
     * 有向环
     */
    private Stack<Integer> cycle;

    /**
     * 检测有向环
     * @param digraph 有向图
     */
    public DirectedCycle(Digraph digraph) {
        marked  = new boolean[digraph.V()];
        onStack = new boolean[digraph.V()];
        edgeTo  = new int[digraph.V()];
        for (int v = 0; v < digraph.V(); v++) {
            if (!marked[v] && cycle == null) {
                dfs(digraph, v);
            }
        }
    }

    /**
     * 深度优先检测有向环
     * @param digraph   有向图
     * @param s 起点
     */
    private void dfs(Digraph digraph, int s) {
        Stack<Entry<Integer, Iterator<Integer>>> path = new Stack<>();
        // marked[v] = true;
        if (!marked[s]) {
            // 键值对起点-起点对应邻接表迭代器压入栈中
            marked[s] = true;
            onStack[s] = true;
            Iterable<Integer> iterable = digraph.adj(s);
            Iterator<Integer> it;
            if (iterable != null && (it = iterable.iterator()) != null){
                path.push(new Entry<>(s, it));
            }
        }
        deepLevel:
        while (!path.isEmpty()) {
            Entry<Integer, Iterator<Integer>> entry = path.pop();
            int x;
            Iterator<Integer> it = entry.getValue();
            Integer f = entry.getKey();
            while (it.hasNext()) {
                // 当前顶点对应的邻接表迭代器还有元素，获取下一个元素
                x = it.next();
                if (cycle != null) {
                    return;
                } else if (!marked[x]) {
                    // 顶点未被标记，标记顶点且标记路径x->f
                    // f是x所在邻接表对应的顶点
                    marked[x] = true;
                    onStack[x] = true;
                    edgeTo[x] = f;
                   // if (it.hasNext()) {
                    // 邻接表迭代器还有元素，重新压入栈
                    path.push(entry);
                   // }
                    // 按照深度优先原则，把新标记顶点对应的键值对压入栈中，在下次循环时优先访问
                    Iterable<Integer> iterable = digraph.adj(x);
                    if (iterable != null && (it = iterable.iterator()) != null){
                        path.push(new Entry<>(x, it));
                    }
                    continue deepLevel;
                } else if (onStack[x]) {
                    // 存在有向环
                    // 遍历有向路径，构建有向环
                    cycle = new Stack<>();
                    for (int i = f; i != x ; i = edgeTo[i]) {
                        cycle.push(i);
                    }
                    cycle.push(x);
                    cycle.push(f);
                }
            }
            onStack[f] = false;

        }
    }

    /**
     * 是否存在有向环
     * @return {@code true} 存在有向环, {@code false} 否则
     */
    public boolean hasCycle() {
        return cycle != null;
    }

    /**
     * 返回有向环
     */
    public Iterable<Integer> cycle() {
        return cycle;
    }


    /**
     * 证明确实有有向环
     * @return {@code true} 确实存在一个有向环， {@code false}否则
     */
    private boolean check() {

        if (hasCycle()) {
            // verify cycle
            int first = -1, last = -1;
            for (int v : cycle()) {
                if (first == -1) {
                    first = v;
                }
                last = v;
            }
            if (first != last) {
                System.err.printf("cycle begins with %d and ends with %d\n", first, last);
                return false;
            }
        }


        return true;
    }
}